package com.xyhuo.leetcode.january;

import com.xyhuo.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 二叉树的层序遍历Ⅱ
 * https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
 *
 * @time 2024/1/9
 */
public class LevelOrderBottom {

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        search(root, 0);
        List<List<Integer>> ans = new ArrayList<>();
        int size = map.size();
        for (int i = 0; i < size; i++) {
            ans.add(map.get(size - 1 - i));
        }
        return ans;
    }

    private Map<Integer, List<Integer>> map = new HashMap<>();

    private void search(TreeNode root, int step) {
        if (null == root) {
            return;
        }
        List<Integer> list = null;
        if (!map.containsKey(step)) {
            list = new ArrayList<>();
            map.put(step, list);
        } else {
            list = map.get(step);
        }
        list.add(root.val);
        search(root.left, step + 1);
        search(root.right, step + 1);
    }

}
